package util

import (
	"sort"
	"strings"
	"sync"
)

type ItemsAndCount struct {
	Items      []string //频繁数据
	Count      int
	ContainSet *[]int //频繁数据所在的行的索引
}

type L struct {
	Iac     []*ItemsAndCount
	hashSet map[string]int //频繁数据的连接哈希

}

// C 候选集合
type C struct {
	Items       [][]string //候选数据
	ContainSet  []*[]int   //上级频繁数据所在的行的索引
	ContainSet2 []*[]int
}

func (c C) Scan(r int) *L {
	var lock sync.Mutex
	var wg = sync.WaitGroup{}

	var ch = make(chan int, len(c.Items))
	for i := 0; i < len(c.Items); i++ {
		ch <- i
	}
	close(ch)

	var iac = make([]*ItemsAndCount, 0, 1<<10)
	for i := 0; i < 12; i++ {
		wg.Add(1)
		go func() {
			for i1 := range ch {
				var tem = make([]int, 0)
				var l = 0
				var c1, c2 = *c.ContainSet[i1], *c.ContainSet2[i1]
				var p1, p2 = 0, 0
				var l1, l2 = len(c1), len(c2)
				for {
					if c1[p1] > c2[p2] {
						p2++
						if p2 >= l2 {
							break
						}
					} else if c1[p1] < c2[p2] {
						p1++
						if p1 >= l1 {
							break
						}
					} else {
						tem = append(tem, c1[p1])
						l++
						p1++
						p2++
						if p1 >= l1 || p2 >= l2 {
							break
						}
					}
				}
				lock.Lock()
				if l >= r {
					iac = append(iac, &ItemsAndCount{
						Items:      c.Items[i1],
						Count:      l,
						ContainSet: &tem,
					})
				}
				lock.Unlock()

			}
			wg.Done()
		}()

	}
	wg.Wait()
	return &L{

		Iac: iac,
	}
}

//GenC 迭代下一级候选集合
func (l L) GenC() *C {
	var length = len(l.Iac[0].Items)

	var lock1 = &sync.Mutex{}
	var acceptArr = make([][]string, 0, 4096)
	var containSet = make([]*[]int, 0, 4096)
	var containSet2 = make([]*[]int, 0, 4096)

	var lock2 = &sync.Mutex{}
	var set = make(map[string]struct{}, 1<<13) //保存所有已经出现过的组合，防止重复

	//l.Iac = sortIac1(l.Iac)
	sortIac(l.Iac)
	l.hashSet = getSet(&l)

	var messageChan = make(chan int, len(l.Iac)) //分发任务的chan
	for i := 0; i < len(l.Iac)-1; i++ {
		messageChan <- i
	}
	close(messageChan)
	var wg = sync.WaitGroup{}

	for n := 0; n < 12; n++ {
		wg.Add(1)
		go func() {
			for i := range messageChan {
				for j := i + 1; j < len(l.Iac); j++ {
					length = len(l.Iac[0].Items)
					var flagI = false
					if length == 1 {
						lock1.Lock()
						if l.Iac[i].Items[0] < l.Iac[j].Items[0] {
							acceptArr = append(acceptArr, []string{l.Iac[i].Items[0], l.Iac[j].Items[0]})
						} else {
							acceptArr = append(acceptArr, []string{l.Iac[j].Items[0], l.Iac[i].Items[0]})
						}
						containSet = append(containSet, l.Iac[i].ContainSet)

						containSet2 = append(containSet2, l.Iac[j].ContainSet)

						lock1.Unlock()
					} else {
						var mpr = make(map[string]struct{})
						for _, v2 := range l.Iac[i].Items {
							mpr[v2] = struct{}{}
						}
						for _, v2 := range l.Iac[j].Items {
							mpr[v2] = struct{}{}
						}

						if len(mpr) == length+1 {
							var dif = make([]string, 0, length+1)
							for key, _ := range mpr {
								dif = append(dif, key)
							}
							sort.Strings(dif)
							var sb = strings.Builder{}
							for _, v := range dif {
								sb.WriteString(v)
								sb.WriteByte('|')
							}
							//判断当前组合是否出现过
							lock2.Lock()
							if _, ok := set[sb.String()]; ok {
								lock2.Unlock()
								continue

							}
							set[sb.String()] = struct{}{}
							lock2.Unlock()
							sb.Reset()
							var minLen1 = len(*l.Iac[i].ContainSet)
							var minLen2 = len(*l.Iac[j].ContainSet)
							var minArr1 = i
							var minArr2 = j
							if minLen1 > minLen2 {
								minArr2, minArr1 = minArr1, minArr2
								minLen1, minLen2 = minLen2, minLen1
							}
							var flag2 = true
							//遍历子集并判断是否存在频繁集合中
							for i := 0; i < len(dif); i++ {
								for j := 0; j < len(dif); j++ {
									if i == j {
										continue
									}
									sb.WriteString(dif[j])
									sb.WriteByte('|')
								}
								if ind, ok := l.hashSet[sb.String()]; !ok {
									flag2 = false
									break
								} else {
									var len3 = len(*(l.Iac[ind].ContainSet))
									if len3 < minLen2 {
										if len3 < minLen1 {
											minArr2 = minArr1
											minArr1 = ind
											minLen2 = minLen1
											minLen1 = len3
										} else if len3 > minLen1 {
											minArr2 = ind
											minLen2 = len3
										}
									}
								}
								sb.Reset()
							}
							if flag2 {
								lock1.Lock()
								acceptArr = append(acceptArr, dif)
								containSet = append(containSet, l.Iac[minArr1].ContainSet)
								containSet2 = append(containSet2, l.Iac[minArr2].ContainSet)
								lock1.Unlock()
							}
						} else {
							flagI = true
						}

					}

					if flagI {
						break
					}

				}

			}
			wg.Done()
		}()
	}
	wg.Wait()

	return &C{Items: acceptArr,
		ContainSet:  containSet,
		ContainSet2: containSet2,
	}
}

func sortIac(slice []*ItemsAndCount) {
	sort.Slice(slice, func(i, j int) bool {
		var l1, l2 = len(slice[i].Items), len(slice[j].Items)
		var flag bool
		var min int
		if l1 < l2 {
			flag = true
			min = l1
		} else {
			flag = false
			min = l2
		}
		for ind := 0; ind < min; ind++ {
			if slice[i].Items[ind] < slice[j].Items[ind] {
				return true
			} else if slice[i].Items[ind] > slice[j].Items[ind] {
				return false
			}
		}
		return flag
	})
}

//计算每项数据字典排序后连接的map
func getSet(l *L) map[string]int {
	var hashSet = make(map[string]int)
	var sb = strings.Builder{}
	for i := 0; i < len(l.Iac); i++ {
		for _, v := range l.Iac[i].Items {
			sb.WriteString(v)
			sb.WriteByte('|')
		}
		hashSet[sb.String()] = i
		sb.Reset()
	}
	return hashSet
}

func sortIac1(slice []*ItemsAndCount) []*ItemsAndCount {
	if len(slice) < 36 {
		sortIac(slice)
		return slice
	}
	var off = 0
	var block = len(slice)/12 + 1
	var wg = &sync.WaitGroup{}
	for i := 0; i < 12; i++ {
		wg.Add(1)
		go func(begin, end int) {

			if end > len(slice) {
				end = len(slice)
			}
			if begin > end {
				wg.Done()
				return
			}
			sort.Slice(slice[begin:end], func(i, j int) bool {
				i += begin
				j += begin
				var l1, l2 = len(slice[i].Items), len(slice[j].Items)
				var flag bool
				var min int
				if l1 < l2 {
					flag = true
					min = l1
				} else {
					flag = false
					min = l2
				}

				for ind := 0; ind < min; ind++ {
					if slice[i].Items[ind] < slice[j].Items[ind] {
						return true
					} else if slice[i].Items[ind] > slice[j].Items[ind] {
						return false
					}
				}
				return flag
			})
			wg.Done()
		}(off, off+block)
		off += block
	}
	wg.Wait()
	var sl = make([]*ItemsAndCount, block)
	var si = 0
	copy(sl, slice[0:block])
	for i := 1; i < 12; i++ {
		begin := i * block
		end := begin + block
		if end > len(slice) {
			end = len(slice)
		}
		if begin >= end {
			continue
		}
		si = 0
		tem := make([]*ItemsAndCount, len(sl)+(end-begin))
		temI := 0
		l1 := len(sl)
		for {
			if ju(sl[si], slice[begin]) {
				tem[temI] = sl[si]
				si++
				temI++
				if si >= l1 {
					for begin < end {
						tem[temI] = slice[begin]
						temI++
						begin++
					}
					break
				}
			} else {
				tem[temI] = slice[begin]
				begin++
				temI++
				if begin >= end {
					for si < l1 {
						tem[temI] = sl[si]
						si++
						temI++

					}
					break
				}
			}

		}
		sl = tem

	}
	return sl

}
func ju(i *ItemsAndCount, j *ItemsAndCount) bool {

	var l1, l2 = len(i.Items), len(j.Items)
	var flag bool
	var min int
	if l1 < l2 {
		flag = true
		min = l1
	} else {
		flag = false
		min = l2
	}

	for ind := 0; ind < min; ind++ {
		if i.Items[ind] < j.Items[ind] {
			return true
		} else if i.Items[ind] > j.Items[ind] {
			return false
		}
	}
	return flag
}
